package cn.njupt.doublecirclelist;

//双向循环链表
public class LinkedList<E> extends AbstractList<E> {

    private Node<E> first;

    private Node<E> last;


    private static class Node<E> {
        E element;
        Node<E> next;
        Node<E> prev;

        public Node(Node<E> prev,E element, Node<E> next) {
            this.prev=prev;
            this.element = element;
            this.next = next;
        }


        @Override
        public String toString() {
            StringBuilder sb=new StringBuilder();
            if(prev==null){
                sb.append("null");
            }else{
                sb.append(prev.element);
            }
            sb.append(":"+element+":");
            if(next==null){
                sb.append("null");
            }else{
                sb.append(next.element);
            }
            return sb.toString();
        }
    }


    @Override
    public void clear() {
        size = 0;
        first = null;
        last=null;
    }

    /**
     * 得到索引位置上的指定节点
     * @param index
     * @return
     */
    private Node<E> getIndexNode(int index) {
        judgeIndexOutOfBounds(index);
        Node curNode=null;
        if(index<(size>>1)){
            //从前往后
            curNode=first;
            for (int i = 0; i < index; i++) {
                curNode=curNode.next;
            }
        }else{
            curNode=last;
            for (int i = size-1; i >index ; i--) {
                curNode=curNode.prev;
            }
        }
        return curNode;
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        Node<E> node=first;
        sb.append("size="+size+",[");
        for (int i = 0; i <size; i++) {
            sb.append(node);
            if(i!=size-1){
                sb.append(",");
            }
            node=node.next;
        }
        sb.append("]");
        return sb.toString();
    }




    /**
     * 在指定位置插入元素
     * @param index
     * @param element
     */
    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        if(index==size){  //在尾部添加数据,注意0和尾部
            Node curNode=new Node(last,element,first);
            if(last==null){ //0位置添加
                last=curNode;
                first=curNode;
                curNode.prev=curNode;
                curNode.next=curNode;
            }else{
                last.next=curNode;
                last=curNode;
                last.next=first;
                first.prev=last;
            }
        }else{  //在头部或者在中间添加数据，注意头部和中间位置
            Node<E> indexNode = getIndexNode(index);
            Node<E> prev=indexNode.prev;
            Node curNode=new Node(prev,element,indexNode);
            indexNode.prev=curNode;
            if(last==curNode.prev){  //说明是在头结点
                first=curNode;
                last.next=first;
            }else{
                prev.next=curNode;
            }
        }
        size++;
    }

    /**
     * 自己写的移除操作，没有官方写的好
     * @param index
     */
    @Override
    public void remove(int index) {
        judgeIndexOutOfBounds(index); //[0,size-1]
        Node<E> curNode = getIndexNode(index);
        if (index == 0) {
            first = first.next;
            if(size==1){
                last=null;
                first=null;
            }else{
                first.prev=last;
                last.next=first;
            }
        } else if(index==(size-1)){
            last=curNode.prev;
            last.next=first;
            first.prev=last;
        }else{
            curNode.prev.next=curNode.next;
            curNode.next.prev=curNode.prev;
        }
        size--;
    }

    /**
     * 这边写的是双向链表的删除方法，不是双向循环链表
     * @param index
     */
    public void removeStrength(int index){
        judgeIndexOutOfBounds(index);
        Node<E> node= getIndexNode(index);
        Node<E> prev=node.prev;
        Node<E> next=node.next;
        if(prev==null){ //说明是第0个节点
            first=next;
        }else{
            prev.next=next;
        }

        if(next==null){ //说明是最后一个节点
            last=prev;
        }else {
            next.prev=prev;
        }
        size--;
    }






    @Override
    public E set(int index, E element) {
        judgeIndexOutOfBounds(index);
        Node<E> oldNode = getIndexNode(index);
        oldNode.element = element;
        return oldNode.element;
    }

    @Override
    public E get(int index) {
        judgeIndexOutOfBounds(index);
        return getIndexNode(index).element;
    }


    @Override
    public int indexOf(E element) {
        Node<E> node = first;
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (node.element == null) return i;
                node = node.next;
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(node.element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

}
